The present invention relates to an extended key generator, encryption/decryption unit, and storage medium, which are applied to secret key block cipher.
In the fields of recent computer and communication technologies, a cryptography technology for transmitting encrypted transmission data, and restoring the received contents by decrypting received data is prevalent. In such cipher technology, a cryptography algorithm that uses a secret key (to be referred to as a common key hereinafter) in both encryption and decryption is called common key cipher. In common key cipher, an input message is segmented into input blocks each having a fixed length, and the segmented blocks undergo randomization based on a key to generate ciphertext. As such common key cipher, a scheme called, e.g., DES (data encryption standard) is prevalently used.
In encryption based on DES, as shown in FIG. 1A, data obtained via initial permutation IP of plaintext undergoes 16 processes using round functions. Furthermore, the data that has undergone 16 rounds undergoes inverse permutation Ip−1 of the initial permutation, thus obtaining ciphertext. On the other hand, by giving an extended key generated from the original key to each round function, a process in that round function is executed.
That is, an encryption apparatus based on DES has as principal building components a data randomization part for randomizing data to be encrypted using a large number of round functions, and a key generator for giving an extended key to each round function of the data randomization part. Note that the conventional key generator generates a key by rearranging bits using a table or wiring lines, using the same key as that of a data encryption unit, or randomly extracting from key bits.
In decryption based on DES, as shown in FIG. 1B, data to be decrypted undergoes 16 rounds in an order inverse to that upon encryption. Hence, a key generator generates extended keys in order from a key used in the last round function upon encryption.
The first merit in DES lies in the arrangement of encryption and decryption circuits; they can commonize most components. That is, as shown in FIGS. 1A and 1B, an identical circuit is used for the round functions of the data randomization part, although the input order of extended key is reversed upon encryption and decryption.
The second merit of DES is a small number of keys to be managed, since encryption and decryption are done using a single common key. In DES, in order to generate extended keys in normal and reverse orders on the basis of a sole common key, the key generator executes the following processes.
That is, a common key undergoes left rotate-shift (left rotation) to generate each extended key. Note that the total value of rotation amounts is defined to match the number of bits of the common key, and an intermediate key is finally returned to an initial state (common key). In this manner, the last extended key upon encryption can be generated to have the same value as that of the first extended key upon decryption. Upon decryption, a common key undergoes right rotate-shift (right rotation) to generate extended key in reverse order.
However, since the processes of the key generator are implemented by only permutation processes in DES, key generally called weak keys which have low security are present. Note that the weak keys mean extended keys which have identical values, and include a case wherein all extended keys K1 to K16 are equal to each other (K1=K2= . . . K16), and a case wherein half extended keys K1 to K8 and K9 to K16 are equal to each other (K1=K16, K2=K15, . . . , K8=K9).
However, generation of such weak keys is not a menace but can be sufficiently prevented by adding a device for removing input of a common key having a pattern for generating weak keys to an extended key generator, or adding to a cipher generation apparatus a device for determining whether or not generated extended keys are weak keys, and removing them if they are weak keys.
However, when such device that prevents generation of weak keys is added, the prices of the extended key generator and encryption/decryption unit rise, and also their circuit scales increase.
In addition to DES, a cryptosystem that can offer cryptological robustness upon using different extended keys in units of round functions by preventing generation of weak keys, and can improve the cryptological robustness has been demanded.
As described above, in the conventional extended key generator and encryption/decryption unit, when a device that prevents generation of weak keys is added to avoid low security, the prices of the extended key generator and encryption/decryption unit rise, and also their circuit scales increase.
Even when generation of weak keys is prevented, processes in the key generator does not so contribute to improvement in cryptological robustness, and improvement in cryptological robustness is demanded.